#pragma once

//#include<algorithm>
#include<iostream>
#include<vector>
#include"line.h"

using namespace std;

namespace wx
{
	
	template<class T>
	struct ListNode
	{
		T _data;
		ListNode<T>* _next;
		ListNode(const T& val = 0)
			:_data(val),
			_next(nullptr)
		{ }

	};

	template<class T>
	class SingleList;

	template<typename T>
	sequence<T> listtoline(SingleList<T>& l1, SingleList<T>& l2) 
	{
		ListNode<T>* cur1 = l1._root;
		ListNode<T>* cur2 = l2._root;

		sequence<T> s;

		while (cur1) 
		{
			s.Insert(cur1->_data);
			cur1 = cur1->_next;
		}
		while (cur2) 
		{
			s.Insert(cur2->_data);
			cur2 = cur2->_next;
		}

		s.Reverse();
		return s;
	}

	template<class T>
	class SingleList
	{
		typedef ListNode<T> Node;
	public:
		template<typename T>
		friend sequence<T> listtoline(SingleList<T>& l1, SingleList<T>& l2);

		void insert(const T& val) 
		{
			if (_root == nullptr) 
			{
				_root = new Node(val);
			}
			else {
				Node* cur = _root;
				Node* parent = nullptr;
				Node* newnode = new Node(val);
				while (cur && val > cur->_data) 
				{
					parent = cur;
					cur = cur->_next;
				}
				if (parent == nullptr) 
				{ 
					newnode->_next = _root;
					_root = newnode;
				}
				else 
				{
					parent->_next = newnode;
					newnode->_next = cur;
				}
				newnode = nullptr;
			}
		}

		void Reverse() 
		{
			if (_root == nullptr || _root->_next == nullptr) 
			{
				return;
			}
			Node* prev = nullptr;
			Node* cur = _root;
			Node* next = nullptr;
			while (cur != nullptr) 
			{
				next = cur->_next;
				cur->_next = prev;
				prev = cur;
				cur = next;
			}
			_root = prev;
		}

		void print() const 
		{
			ListNode<T>* cur = _root;
			while (cur != nullptr) {
				cout << cur->_data << " ";
				cur = cur->_next;
			}
			cout << endl;
		}

		~SingleList()
		{
			Node* cur = _root->_next;
			while (cur)
			{
				delete _root;
				_root = cur;
				cur = cur->_next;
			}
			delete _root;
		}

	private:
		Node* _root = nullptr;
	};
}

